// 用了分治的思想 每次找个基数将比基数大的放在右边，小的放在左边，如此往复就行了
function quickSort(arr, low, high) {
    let temp = arr[low];
    let l = low;
    let r = high;
    if (low > high) {
        return;
    }

    while (l < r) {
        while (temp <= arr[r] && l < r) {
            r--;
        }
        while (temp >= arr[l] && l < r) {
            l++;
        }
        if (l < r) {
            let t = arr[r];
            arr[r] = arr[l];
            arr[l] = t;
        }
    }

    arr[low] = arr[r];
    arr[r] = temp;
    quickSort(arr, low, r - 1);
    quickSort(arr, r + 1, high);
}


let array = [1, 4, 3, 5, 6, 2, 1, 0, 4, -1, 6, 9]
quickSort(array, 0, array.length - 1);

console.log(array.toString())
